package com.collections;

/**
 * User: ${bkand1909} (hungle.info@gmail.com)
 * Date: 12/11/12
 * Time: 6:44 PM
 */
public class BinaryIndexedTree {
    private int n;
    private int[] tree;

    public BinaryIndexedTree(int size) {
        this.n = size;
        tree = new int[n + 1];
    }

    public void update(int i, int value) {
        for (; i <= n; i += i & -i)
            tree[i] += value;
    }

    public int get(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i)
            res += tree[i];
        return res;
    }

    public int sum(int left, int right) {
        return get(right) - get(left - 1);
    }
}
